import java.util.ArrayList;
import java.util.List;

class Solution {
    List<List<String>> ret;
    char[][] board;
    boolean[] col;
    boolean[] diag1;
    boolean[] diag2;
    int len = 0;
    public List<List<String>> solveNQueens(int n) {
        ret = new ArrayList<>();
        board = new char[n][n];
        col = new boolean[n];
        diag1 = new boolean[2 * n];
        diag2 = new boolean[2 * n];
        len = n;
        for(int i = 0; i < len; i++){
            for(int j = 0; j < len; j++){
                board[i][j] = '.';
            }
        }

        dfs(0);
        return ret;
    }
    public void dfs(int r){
        // dfs 出口
        if(r == len){
            List<String> path = new ArrayList<>();
            for(int i = 0; i < len; i++){
                path.add(new String(board[i]));
            }
            ret.add(path);
            return;
        }
        // 四个位置挑一个
        for(int i = 0; i < len; i++){
            // 放棋子之前，需要判断能不能放 - 剪枝操作
            if(col[i] == false && diag1[i - r + len] == false && diag2[i + r] == false){
                board[r][i] = 'Q';
                col[i] = true;
                diag1[i - r + len] = true;
                diag2[i + r] = true;
                dfs(r + 1);
                board[r][i] = '.';
                col[i] = false;
                diag1[i - r + len] = false;
                diag2[i + r] = false;
            }
        }
    }
}